Wilcze doły

Limit pamięci: 128 MB

Król Bajtocji, Bajtazar III Zuchwały, planuje najazd na zamek wroga. Zamek jest z trzech stron otoczony niemożliwą do sforsowania fosą, więc Bajtazarowi pozostaje przypuścić atak na czwartą ścianę zamku. Sprawa nie jest jednak taka prosta, gdyż królewscy zwiadowcy donieśli o tym, że wzdłuż tej ściany wróg wykopał głębokie wilcze doły. Bajtazar chciałby zaatakować jak najdłuższy spójny fragment tej ściany. W tym celu będzie musiał zrównać z ziemią niektóre doły. Król postanowił, że część z nich przysypie piachem, a część przykryje Wielką Dechą.

Wzdłuż ściany wykopanych jest dołów. Król Bajtazar posiada worków z piachem. Do przysypania -tego dołu potrzebne jest takich worków. Ponadto, Wielka Decha pozwala na przykrycie sąsiednich dołów.

Pomóż Bajtazarowi znaleźć długość najdłuższego fragmentu ściany, który będzie mógł zaatakować, jeśli optymalnie wykorzysta worki z piachem i Wielką Dechę. Innymi słowy, oblicz, ile maksymalnie kolejnych dołów może zostać zrównanych z ziemią.

Wejście

Pierwszy wiersz standardowego wejścia zawiera trzy liczy całkowite , oraz (, ) pooddzielane pojedynczymi odstępami, oznaczające odpowiednio liczbę dołów, liczbę worków z piachem oraz długość Wielkiej Dechy.

Kolejny wiersz opisuje doły i zawiera ciąg liczb całkowitych () pooddzielanych pojedynczymi odstępami; oznacza liczbę worków potrzebnych do przysypania -tego dołu.

W testach wartych łącznie punktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą długości najdłuższego spójnego fragmentu ściany, na który Bajtazar może przypuścić atak.

Przykład

Dla danych wejściowych:

9 7 2
3 4 1 9 4 1 7 1 3

poprawną odpowiedzią jest:

5

Wyjaśnienie do przykładu: Bajtazar może przysypać doły o numerach 2, 3 i 6 (zużywając do tego celu 6 spośród 7 posiadanych worków z piachem) oraz przykryć Wielką Dechą doły 4 i 5. W ten sposób król zrówna z ziemią pięć kolejnych dołów (o numerach od 2 do 6).

Testy "ocen":

• 1ocen:, , , wszystkie ; można zrównać z ziemią wszystkie doły poza jednym;
• 2ocen: , , , doły o parzystych numerach potrzebują dwóch worków z piachem, zaś doły o nieparzystych numerach potrzebują jednego worka.

Autor zadania: Jacek Tomasiewicz.